#include "insertionsort.h"

namespace simon{

inline int median(int *a, int x, int y, int z){
	if (a[x]>=a[y]){
		if (a[y]>=a[z]){
			return y;
		}else{
			if (a[z]>=a[x]){
				return x;
			}else{
				return z;
			}
		}
	}else{
		if (a[x]>=a[z]){
			return x;
		}else{
			if (a[y]>=a[z]){
				return z;
			}else{
				return y;
			}
		}
	}
}

// .......(i).........(j)......(pivot)
int partition(int *a,int si,int ei, int pivotidex){
	swap(a[pivotidex],a[ei]);//
	int i=si;
	int k=si;
	int pivot = a[ei];
	while(k<ei){
		if (a[k]<pivot){
			//printarray(a,si,ei+1);
			swap(a[k],a[i]);
			//printarray(a,si,ei+1);
			i++;
		}
		k++;
	}
	swap(a[ei],a[i]);
	return i-1;
}

int partition2(int *a,int si,int ei){
	int pivotindex = median(a,si,ei,(ei+si)>>1);
	if(pivotindex!=ei)swap(a[pivotindex],a[ei]);//
	int i=si;
	int k=si;
	int pivot = a[ei];
	while(k<ei){
		if (a[k]<pivot){
			//printarray(a,si,ei+1);
			swap(a[k],a[i]);
			//printarray(a,si,ei+1);
			i++;
		}
		k++;
	}
	swap(a[ei],a[i]);
	return i-1;
}


// array pointer, start index, endindex
void qksort(int *a, int si, int ei){
	if (si>=ei){
		return;
	}
#if 1
	if(ei-si<10){
		insertionsort(a,si,ei);
	}
#endif
	int pi=partition2(a,si,ei);//partition index
	qksort(a,si,pi);
	qksort(a,pi+2,ei);
}

void test1(){
	const int N=200e6;
	int* a=new int[N];
	for(int i=0;i<N;i++){a[i]=i;}
	random_shuffle(a,a+N);
	time_t start,end;
	time (&start);
	//mergesort2(a,0,N-1);
	//mergesort(a,0,N-1);
	//sort(a,a+N);
	//stable_sort(a,a+N);
	qksort(a,0,N-1);
	time (&end);
	double dif = difftime (end,start);
	printf ("It took you %.2lf seconds to sort.\n", dif ); //It took you 31.00 seconds to sort.
	printarray(a,15200,15250);
	delete [] a;
	printf("memnum:%d\n",memnum);
}

}




